package leetcode_1101_1200;

import java.util.ArrayDeque;
import java.util.Deque;

public class LeeCode_1130 {
    public static void main(String[] args) {
        System.out.println(mctFromLeafValues(new int[]{3, 2, 1}));
    }

    private static int mctFromLeafValues(int[] arr) {
        Deque<Integer> stk = new ArrayDeque<>();
        int ans = 0;
        for (int x : arr) {
            while (!stk.isEmpty() && stk.peek() <= x) {
                Integer y = stk.pop();
                if (stk.isEmpty() || stk.peek() > x) {
                    ans += y * x;
                }else {
                    ans += stk.peek() * y;
                }
            }
            stk.push(x);
        }
        while (stk.size() >= 2){
            int y = stk.pop();
            ans += stk.peek() * y;
        }
        return ans;
    }
}
